1. Field of the Invention
The present invention relates to encoding, detection, and decoding of data in communication systems, and, more particularly, to an interleaver and de-interleaver for product code error detection and correction by a receiver.
2. Description of the Related Art
Many digital transmission systems commonly employ techniques for detection of digital data represented by a sequence of symbols. The symbol bits are transferred as a signal through a transmission (i.e., communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered to take place via a transmission channel that has an associated frequency response. Similarly, wired, optical, wireless, and cellular communication systems also transfer encoded data through a channel, which encoded data is then detected and decoded by a receiver. The signal may be read from the channel as a sampled signal (i.e., a sequence of sample values) representing the transmitted encoded data. For processing convenience, the encoding and decoding process is applied to blocks of data, each block representing a portion of the original data sequence.
Encoding data with two-dimensional or higher block codes and subsequent decoding of the encoded data are employed in many systems due to the relatively high coding gain and simple structure of the decoder. Product codes may be employed for encoding of data in which two or more simple codes (known as component codes) are combined to create more powerful encoding schemes. The dimension of the code may be related to the number of component codes.
For example, a product code may employ a parity-bit check code that, for the two-dimensional case, encodes N information bits as two-dimensional data words (e.g., n1 words having n2 information bits, or n2 words having n1 information bits). Each data word represents a vector in a corresponding dimension, and n1 and n2 are integers greater than 0. The product code encoding of the data (i.e., the N information bits) are ordered in a rectangular matrix u, and the encoding may be a row vector (e.g., n2 information bits) by column vector (e.g., n1 information bits) combination to form the rectangular matrix u. The combination may be Galois field (GF)(2) addition, multiplication, or linear operation of the binary values. For example, a sequence of N information bits (e.g., a block of data) may be formed as an (n1×n2) matrix of information bits, with N=n1n2. The product code encoding of the data also includes row- and column-wise parity bits pr and pc, respectively, as error detection and correction information. Horizontal rows are formed from n2 code words of an (n1, k1) block code Cr having rate R1=(n1/k1) (here, k1 is the total length of a row, and the length of the parity bit information for each row is k1−n1). Vertical columns are formed from n1 code words of an (n2, k2) block code Cc having rate R2=(n2/k2) (here, k2 is the total length of a column, and the length of the parity bit information for each column is k2−n2).
The block of data encoded with the product code is typically transmitted as a serial block of encoded data. Product codes typically exhibit optimum performance with respect to coding gain when correcting for single one-bit errors when single-bit parity check codes are employed on a per dimension basis. Only single, one-bit errors may be detected and corrected because of parity-check cancellation arising from an even number of errors occurring in a row or in a column and parity-check positional ambiguities associated with multiple one-bit errors. For an example of this positional ambiguity in a square, product code matrix with single-bit parity check codes, let the first element of the first row be in error, and the second element of the second row be in error (errors along the forward diagonal). Both the first and second row-wise and first and second column-wise parity bits will indicate an error, but they will also indicate an error if the second element of the first row and the first element of the second row is in error (errors in the reverse diagonal). Availability of soft information may aide in soft decoding to distinguish this type of ambiguity.
Detection and correction of higher numbers of errors, especially higher numbers of consecutive errors, may add excessive overhead in terms of error detection information (e.g., parity bits), reducing overall system throughput. Errors in data at the receiver may be caused by incorrect decisions of the detection and/or decoding process because of signal degradation. Signal degradation occurs from added random and/or burst noise as the signal passes through the communication channel.
For some product codes, the resulting output sequence may include symbol patterns that are particularly susceptible to detection error. For example, a sequence of all “1's may be difficult to detect if the receiver's sample timing is out of phase with the sequence symbol timing. Consequently, an interleaver design might include logic that avoids these patterns.
A characteristic of some communication channels is the addition of “bursty” noise. Such noise may corrupt a transmitted signal for a period of time equivalent to the period of several transmitted symbols (either data or encoded data). Bursty noise may cause burst errors in the received data. To minimize the effect of burst errors, many communication systems include an interleaver in the transmitter and a corresponding de-interleaver in the receiver. Interleaving is a mapping f(*) that generally comprises receiving a block of data having BLK values (i.e., BLK is the block length and BLK is an integer greater than one), and rearranging the order of the BLK values in the block. Interleaving may also be employed, for example, to remove non-random sequences of values in a data stream. By interleaving the symbols in a block of data prior to transmission through the channel, the de-interleaving process distributes the burst errors throughout the de-interleaved block.
The term “output channel sample” refers to a sample of encoded data from the transmission channel generated through the sampling process of the receiver. A receiver typically includes a detector to detect the sequence of symbol bits representing the encoded data from the output channel samples. A decoder receives the detected symbol sequence from the detector and decodes the sequence of symbol bits to reconstruct the data. The decoder may be a simple decoder reversing the encoding process, or an iterative decoder that repetitively decodes the data until a predetermined decoding metric, such as a maximum bit-error rate (BER) threshold, is satisfied. The detector may typically employ a partial response, maximum-likelihood (PRML) algorithm (e.g., Viterbi algorithm (VA)), a maximum a posterior (MAP) algorithm, or a soft-output Viterbi algorithm (SOVA). The decoder may typically use the soft information generated from the detector and employ soft decoding schemes.
These algorithms used by detectors and/or decoders typically determine a maximum-likelihood path through a trellis of states. The path represents a sequence of decisions for symbols corresponding to the received output channel samples. However, in situations where the received signal has low signal-to-noise ratio (SNR), the algorithm may determine an incorrect path through the trellis, thereby generating an incorrect sequence of decisions for a corresponding sequence of output channel samples. Such sequence of errors is commonly termed an “error event” of the detection algorithm. For some error events, the decision for the sequence of received bits may generate a long sequence of errors, which are thus inserted into the detected encoded data prior to decoding. Some detection algorithms used in a particular implementation are optimized based on channel memory, SNR, and impulse response, and indirectly with respect to dominant error events.
Consequently, an interleaver should have good performance for i) single error event detection and correction, ii) multiple error event detection and correction, and iii) avoidance of typical product code error patterns.